package br.edu.ufcg.splab.simulator.jgrapht;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.BronKerboschCliqueFinder;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

import br.edu.ufcg.splab.generator.TestCase;
import br.edu.ufcg.splab.generator.TestSuite;
import br.edu.ufcg.splab.techniques.reduction.functions.similarity.DistanceFunction;
import br.edu.ufcg.splab.techniques.reduction.strategies.SimilarityMatrix;

public class CliqueFinder implements InterfaceCliqueFinder{

	private Map<Integer, TestCase> mapTestSuite;

	public Collection<Set<TestCase>> getAllMaximalCliques(TestSuite testSuite, DistanceFunction function, double minimumValue){
		createMapTestSuite(testSuite);	
		
		Collection<Set<TestCase>> allCliques = new HashSet<Set<TestCase>>();
		
		UndirectedGraph<String, DefaultEdge> graph = createUndirectedGraph(testSuite, function, minimumValue);
		BronKerboschCliqueFinder<String, DefaultEdge> finder =  new BronKerboschCliqueFinder<String, DefaultEdge>(graph);
		Collection<Set<String>> cliques = finder.getAllMaximalCliques();
		for(Set<String> set:cliques){
			Set<TestCase> clique = new HashSet<TestCase>();
			for (String vertex : set) {
				clique.add(mapTestSuite.get(new Integer(vertex)));
			}
			allCliques.add(clique);
		}	
		return allCliques;
	}

	
	public Collection<Set<TestCase>> getAllCliques(TestSuite testSuite, DistanceFunction function, double minimumValue){
		createMapTestSuite(testSuite);	
		
		Collection<Set<TestCase>> allCliques = new HashSet<Set<TestCase>>();
		
		UndirectedGraph<String, DefaultEdge> graph = createUndirectedGraph(testSuite, function, minimumValue);
		BronKerboschCliqueFinder<String, DefaultEdge> finder =  new BronKerboschCliqueFinder<String, DefaultEdge>(graph);
		Collection<Set<String>> maximalCliques = finder.getAllMaximalCliques();		
		Collection<Set<String>> cliques = new HashSet<Set<String>>();
		for(Set<String> set:maximalCliques){
			Set<Set<String>> ss = this.buildPowerSet(set);
			cliques.addAll(ss);
		}	
		
		for(Set<String> set:cliques){
			Set<TestCase> clique = new HashSet<TestCase>();
			for (String vertex : set) {
				clique.add(mapTestSuite.get(new Integer(vertex)));
			}
			allCliques.add(clique);
		}	
		return allCliques;
	}
	
	public Collection<Set<TestCase>> getAllCliques(UndirectedGraph<String, DefaultEdge> graph, TestSuite testSuite){
		createMapTestSuite(testSuite);	
		
		Collection<Set<TestCase>> allCliques = new HashSet<Set<TestCase>>();
		
		BronKerboschCliqueFinder<String, DefaultEdge> finder =  new BronKerboschCliqueFinder<String, DefaultEdge>(graph);
		Collection<Set<String>> maximalCliques = finder.getAllMaximalCliques();		
		Collection<Set<String>> cliques = new HashSet<Set<String>>();
		for(Set<String> set:maximalCliques){
			Set<Set<String>> ss = this.buildPowerSet(set);
			cliques.addAll(ss);
		}	
		
		for(Set<String> set:cliques){
			Set<TestCase> clique = new HashSet<TestCase>();
			for (String vertex : set) {
				clique.add(mapTestSuite.get(new Integer(vertex)));
			}
			allCliques.add(clique);
		}	
		return allCliques;
	}

	/*
	 * Creates an undirected graph from the test cases that fail and the relationship among this test cases.
	 */
	private UndirectedGraph<String, DefaultEdge> createUndirectedGraph(TestSuite testSuite, DistanceFunction function, double minimumValue){
		SimilarityMatrix matrix = new SimilarityMatrix();
		double[][] m = matrix.createMatrix(testSuite, function);		
		
		SimpleGraph<String, DefaultEdge> graph = new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
	
		List<Integer> vertices = new ArrayList<Integer>();
		for(TestCase tc: testSuite){
			 vertices.add(this.getValueTestCase(tc));
			 graph.addVertex(Integer.toString(this.getValueTestCase(tc)));
			 
		}
		
		for (int line = 0; line < m.length; line++) {
			for (int column = line + 1; column < m.length; column++) {
				if(m[line][column] >= minimumValue){
					Integer v1 = vertices.get(line);
					Integer v2 = vertices.get(column);
					graph.addEdge(v1.toString(), v2.toString());
				}
			}
		}
				
		return graph;
	}
	
	/*
	 * Returns the key to which the specified test case is mapped,
     * or -1 if this map contains no mapping for the test case.
	 * @param testCase The test case whose associated key is to be returned.
	 * @return The key to which the specified test case is mapped or -1 
	 * if this map contains no mapping for the test case.
	 */
	private int getValueTestCase(TestCase testCase){
		if(mapTestSuite.containsValue(testCase)){
			Set<Entry<Integer, TestCase>> set = mapTestSuite.entrySet();
			for(Entry<Integer, TestCase> entry:set){
				if(entry.getValue().equals(testCase)){
					return entry.getKey();
				}
			}
		};
		return -1;
	}
	
	
	/*
	 * Creates the map to which the test cases are mapped.
	 */
	private void createMapTestSuite(TestSuite testSuite){
		mapTestSuite = new HashMap<Integer, TestCase>();
		int i = 1;
		for(TestCase testCase: testSuite.getTestSuite()){
			mapTestSuite.put(i++, testCase);
		}
	}
	
	
	private Set<Set<String>> buildPowerSet(Set<String> inputSet){
		Set<Set<String>> subSets = new HashSet<Set<String>>();
		for(String addToSets:inputSet) {
		    List<Set<String>> newSets = new ArrayList<Set<String>>();
		    for(Set<String> curSet:subSets) {
		        Set<String> copyPlusNew = new HashSet<String>();
		        copyPlusNew.addAll(curSet);
		        copyPlusNew.add(addToSets);
		        newSets.add(copyPlusNew);
		    }
		    Set<String> newValSet = new HashSet<String>();
		    newValSet.add(addToSets);
		    newSets.add(newValSet);
		    subSets.addAll(newSets);
		}
		return subSets;
	}
	
}